﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Text;

namespace eu.h8me.Parsing.LexerLib {

    // Character range helper class.
    internal class CharRange {

        // Helper delegate type.
        public delegate CharRange Process(CharRange range);

        // Constants.
        public const int MIN_VALUE = Char.MinValue;
        public const int MAX_VALUE = Char.MaxValue + 1;

        // Static variables.
        public static CharRange ANY = new CharRange(Char.MinValue, Char.MaxValue) & !new CharRange('\n');
        public static CharRange LOWERCASE = new CharRange('a', 'z');
        public static CharRange UPPERCASE = new CharRange('A', 'Z');

        // Data.
        private List<Range> _Ranges;

        // Helper constructor with empty range.
        private CharRange(List<Range> ranges) {
            // No specific construction.
            _Ranges = ranges;
        }

        // Constructor without range.
        public CharRange(char chr) {
            // Store data.
            _Ranges = new List<Range>() { new Range(chr, chr + 1) };
        }

        // Constructor with range.
        public CharRange(char start, char stop) {
            // Store data.
            _Ranges = new List<Range>() { new Range(start, stop + 1) };
        }

        // Fetch range count.
        public int Count {
            get {
                // Return range count.
                return _Ranges.Count;
            }
        }

        // Fetch immediate range.
        public Range this[int idx] {
            get {
                // Return range at index.
                return _Ranges[idx];
            }
        }

        // Character range union.
        public static CharRange operator |(CharRange r1, CharRange r2) {
            // Build a range of the union.
            return BuildRange(r1, r2, delegate(bool first, bool second) { return first || second; });
        }

        // Character range intersection.
        public static CharRange operator &(CharRange r1, CharRange r2) {
            // Build a range of the intersection.
            return BuildRange(r1, r2, delegate(bool first, bool second) { return first && second; });
        }

        // Character range addition with displacement.
        public static CharRange operator +(CharRange r, int disp) {
            // Walk ranges, adding value.
            List<Range> ranges = new List<Range>();
            foreach( Range range in r._Ranges )
                ranges.Add(new Range(range[0] + disp, range[1] + disp));

            // Return updated char range.
            return new CharRange(ranges);
        }

        // Character range inversion.
        public static CharRange operator !(CharRange r) {
            // Walk ranges, building inverses.
            List<Range> ranges = new List<Range>();
            int laststop = MIN_VALUE;
            foreach( Range range in r._Ranges ) {
                if( laststop < range[0] ) {
                    // Last stop is smaller than this start; attach element.
                    ranges.Add(new Range(laststop, range[0]));
                    laststop = range[1];
                }
            }

            // Check for final range.
            if( laststop < MAX_VALUE )
                ranges.Add(new Range(laststop, MAX_VALUE));

            // Return result.
            return new CharRange(ranges);
        }

        // Function yielding merged set with delegate.
        private static CharRange BuildRange(CharRange r1, CharRange r2, RangesCallback cb) {
            // Build return range.
            List<Range> ranges = new List<Range>();
            foreach( Range range in Ranges(r1, r2, cb) ) {
                // Check whether we should merge ranges.
                if( ranges.Count > 0 && ranges[ranges.Count - 1][1] == range[0] )
                    // Yes, end of last range is start of this range.
                    ranges[ranges.Count - 1] = new Range(ranges[ranges.Count - 1][0], range[1]);
                else
                    // No, is a new range.
                    ranges.Add(range);
            }

            // Create new char range from list.
            return new CharRange(ranges);
        }

        // Function yielding overlaps.
        private delegate bool RangesCallback(bool first, bool second);
        private static IEnumerable<Range> Ranges(CharRange r1, CharRange r2, RangesCallback cb) {
            // Initialize counters.
            int i = 0;
            int imax = r1._Ranges.Count * 2;
            int j = 0;
            int jmax = r2._Ranges.Count * 2;

            // Initialize present state.
            bool[] present = new bool[2];
            int updaterange;
            bool updatestate;

            // Initialize value state.
            int baseval = MIN_VALUE;
            int nextval;

            // Loop over the present ranges.
            while( i < imax || j < jmax ) {
                // Check which of the two can be advanced.
                if( i < imax && ( ( j < jmax && r1._Ranges[i >> 1][i & 1] < r2._Ranges[j >> 1][j & 1] ) || j == jmax ) ) {
                    // i can be advanced.
                    updaterange = 0;
                    updatestate = ( i & 1 ) == 0;
                    nextval = r1._Ranges[i >> 1][i & 1];
                    ++i;
                } else {
                    // j can be advanced.
                    updaterange = 1;
                    updatestate = ( j & 1 ) == 0;
                    nextval = r2._Ranges[j >> 1][j & 1];
                    ++j;
                }

                // Check whether this is a range (and range is wanted); if so, return it.
                if( baseval < nextval && cb(present[0], present[1]) )
                    yield return new Range(baseval, nextval);

                // Update state.
                present[updaterange] = updatestate;
                baseval = nextval;
            }

            // Check for final element.
            if( baseval < MAX_VALUE && cb(present[0], present[1]) )
                yield return new Range(baseval, MAX_VALUE);
        }

        // Format character range.
        public override string ToString() {
            // Loop over ranges, formatting them.
            StringBuilder rv = new StringBuilder();
            for( int i = 0; i < _Ranges.Count; ++i )
                rv.AppendFormat("{0}{1}", i > 0 ? "," : "", _Ranges[i]);

            // Return string.
            return rv.ToString();
        }

        // Helper callback to invert list.
        public static CharRange Invert(CharRange val) {
            // Return inverse of character range.
            return !val;
        }

        // Helper callback to ignore case of match (very culture agnostic... TODO: test better ways to do this).
        public static CharRange IgnoreCase(CharRange val) {
            // Check for lower and uppercase letters in val and transpose them.
            CharRange lowerUPPER = ( val & LOWERCASE ) + ( 'A' - 'a' );
            CharRange UPPERlower = ( val & UPPERCASE ) + ( 'a' - 'A' );

            // Merge the sets.
            return val | lowerUPPER | UPPERlower;
        }

    }

    // Integer range helper class.
    internal class Range {

        // Data.
        private int _Start;
        private int _Stop;

        // Constructor.
        public Range(int start, int stop) {
            // Store data.
            _Start = start;
            _Stop = stop;
        }

        // Helper start accessor.
        public char Start {
            get {
                // Fetch first element.
                return (char)_Start;
            }
        }

        // Helper stop accessor.
        public char Stop {
            get {
                // Fetch last element.
                return (char)( _Stop - 1 );
            }
        }

        // Index accessor.
        public int this[int idx] {
            get {
                // Return start/stop depending on index.
                return idx != 0 ? _Stop : _Start;
            }
        }

        // Stringification.
        public override string ToString() {
            // Return string form.
            return String.Format("{0}-{1}", _Start, _Stop - 1);
        }

    }

}
